package com.leetcode.study;

import java.util.*;

/**
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
 * 无重复字符的最长子串
 */
public class L3 {
    public static void main(String[] args) {
        String s = "abba";
        System.out.println(lengthOfLongestSubstring(s));

    }

    public static int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int start = 0;

        Map<Character, Integer> map = new HashMap<>();

        for (int end = 0; end < s.length(); end++) {
            char alpha = s.charAt(end);

            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }

            map.put(s.charAt(end), end + 1);
            ans = Math.max(ans, end - start + 1);
        }

        return ans;

        /*// 记录字符上一次出现的位置
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int n = s.length();

        int res = 0;
        int start = 0; // 窗口开始位置
        for(int i = 0; i < n; i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index] + 1);
            res   = Math.max(res, i - start + 1);
            last[index] = i;
        }

        return res;*/
    }
}
